//<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;，如果&nbsp;<code>nums</code>&nbsp;<strong>至少</strong>&nbsp;包含 <code>2</code>&nbsp;个元素，你可以执行以下操作中的&nbsp;<strong>任意</strong>&nbsp;一个：</p>
//
//<ul> 
// <li>选择 <code>nums</code>&nbsp;中最前面两个元素并且删除它们。</li> 
// <li>选择 <code>nums</code>&nbsp;中最后两个元素并且删除它们。</li> 
// <li>选择 <code>nums</code>&nbsp;中第一个和最后一个元素并且删除它们。</li> 
//</ul>
//
//<p>一次操作的&nbsp;<strong>分数</strong>&nbsp;是被删除元素的和。</p>
//
//<p>在确保<strong>&nbsp;所有操作分数相同</strong>&nbsp;的前提下，请你求出&nbsp;<strong>最多</strong>&nbsp;能进行多少次操作。</p>
//
//<p>请你返回按照上述要求&nbsp;<strong>最多</strong>&nbsp;可以进行的操作次数。</p>
//
//<p>&nbsp;</p>
//
//<p><strong class="example">示例 1：</strong></p>
//
//<pre>
//<b>输入：</b>nums = [3,2,1,2,3,4]
//<b>输出：</b>3
//<b>解释：</b>我们执行以下操作：
//- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
//- 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
//- 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
//由于 nums 为空，我们无法继续进行任何操作。
//</pre>
//
//<p><strong class="example">示例 2：</strong></p>
//
//<pre>
//<b>输入：</b>nums = [3,2,6,1,4]
//<b>输出：</b>2
//<b>解释：</b>我们执行以下操作：
//- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
//- 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
//至多进行 2 次操作。
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>2 &lt;= nums.length &lt;= 2000</code></li> 
// <li><code>1 &lt;= nums[i] &lt;= 1000</code></li> 
//</ul>
//
//<div><li>👍 11</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        vector memo(n, vector<int>(n, -1));

        function<int(int)> helper = [&](int t) {
            for (auto& arr : memo) {
                ranges::fill(arr, -1);
            }
            function<int(int, int)> dfs = [&](int s, int e) {
                if (s >= e) return 0;
                if (memo[s][e] >= 0) return memo[s][e];
                int res = 0;
                if (nums[s] + nums[s + 1] == t) {
                    res = max(res, 1 + dfs(s + 2, e));
                }
                if (nums[s] + nums[e] == t) {
                    res = max(res, 1 + dfs(s + 1, e - 1));
                }
                if (nums[e - 1] + nums[e] == t) {
                    res = max(res, 1 + dfs(s, e - 2));
                }
                memo[s][e] = res;
                return res;
            };
            int ans = dfs(0, n - 1);
            return ans;
        };
        unordered_set<int> ts{nums[0] + nums[1], nums[0] + nums[n - 1], nums[n - 2] + nums[n - 1]};
        int ans = 0;
        for(auto & t : ts) {
            ans = max(ans, helper(t));
        }
        return ans;
    }
};

//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    vector<int> data{2,2,1,2,1};
    cout << s.maxOperations(data) << endl;
}
